package com.hyb.algorithm.data.struct.str;

import java.util.Stack;

/**
 * @author: ybhu
 * @create: 2021/09/25 23:13
 * <p>
 * 151. 翻转字符串里的单词
 * https://leetcode-cn.com/problems/reverse-words-in-a-string/
 */
public class ReverseWordsInAString {


    public String reverseWords(String s) {
        //遇到空格 将其打入栈中
        // 然后循环遍历 栈

        int n = s.length();

        char[] arr = s.toCharArray();

        //先全部反转
        reverseWordsArr(arr, 0, n - 1);

        //根据空格 反转每个单词
        reversePerWords(arr);


        return cleanSpace(arr,n);
    }

    // trim leading, trailing and multiple spaces
    String cleanSpace(char[] a, int n) {
        int i = 0, j = 0;

        while (j < n) {
            while (j < n && a[j] == ' ') j++;             // skip spaces
            while (j < n && a[j] != ' ') a[i++] = a[j++]; // keep non spaces
            while (j < n && a[j] == ' ') j++;             // skip spaces
            if (j < n) a[i++] = ' ';                      // keep only one space
        }

        return new String(a).substring(0, i);
    }

    public void reversePerWords(char[] arr) {
        int i = 0;
        int j = 0;
        int n = arr.length;
        while (i < n) {
            //i 跳过前面的空格
            while (i < j || (i < n && arr[i] == ' ')) {
                i++;
            }
            // j跳过非空格
            while (j < i || (j < n && arr[j] != ' ')) {
                j++;
            }

            reverseWordsArr(arr, i, j);
        }
    }

    public void reverseWordsArr(char[] arr, int i, int j) {

        while (i < j) {
            char temp = arr[i];
            arr[i++] = arr[j];
            arr[j--] = temp;
        }
    }


    public String reverseWordsByStack(String s) {
        //遇到空格 将其打入栈中
        // 然后循环遍历 栈

        int n = s.length();
        Stack<String> stack = new Stack<>();

        int start = 0;
        int end = n - 1;
        while (s.charAt(start) == ' ') {
            start++;
        }

        while (s.charAt(end) == ' ') {
            end--;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = start; i <= end; i++) {
            if (s.charAt(i) == ' ') {
                //很重要 判断是否是重复的 空格
                if (sb.length() != 0) {
                    stack.push(sb.toString());
                    sb = new StringBuilder();
                }
            } else if (i == end) {
                sb.append(s.charAt(i));
                stack.push(sb.toString());
            } else {
                sb.append(s.charAt(i));
            }
        }

        StringBuilder resStringBuilder = new StringBuilder();
        int size = stack.size();
        int i = 0;
        while (!stack.isEmpty()) {

            String tval = stack.pop();
            resStringBuilder.append(tval);

            if (i != size - 1) {
                resStringBuilder.append(" ");
            }
            i++;
        }

        return resStringBuilder.toString();

    }


}
